package psn.zjk.career.interview.algorithm;

/**
 * @Description 给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
 * <p>
 * 现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
 * <p>
 * 花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
 * <p>
 * 请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
 * 输出：3
 * 解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
 * 现在需要制作 3 束花，每束只需要 1 朵。
 * 1 天后：[x, _, _, _, _]   // 只能制作 1 束花
 * 2 天后：[x, _, _, _, x]   // 只能制作 2 束花
 * 3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3
 * <p>
 * 来源：力扣（LeetCode4）
 * 链接：https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @User zero
 * @Datetime 2021/5/9 8:05
 */
public class LeetCode1482 {

    public int minDays(int[] bloomDay, int m, int k) {
        //园中花数少于需要的花数
        if (bloomDay.length < m * k) {
            return -1;
        }
        //第n天能得到的花数
        int count = 0;
        int low=0;
        int high=0;
        for (int i : bloomDay) {
            high=Math.max(high,i);
        }
        while (low<high) {
            int n=(low+high)/2;
            int x=0;//连续的朵数
            for (int i = 0; i < bloomDay.length; i++) {
                if (bloomDay[i] <= n) {
                    if (++x==k){//连续的k朵，花数+1，连续的朵数x重置
                        count++;
                        x=0;
                    }
                }else{
                    x=0;
                }
            }
            if (count >= m){//成功
                high=n;
            }else {
                low=n+1;
            }
            n=(low+high)/2;
            count=0;
        }
        return high;
    }


    public static void main(String[] args) {
//        int[] bloomDay = {100000000,100000000};
//        System.out.println(new LeetCode1482().minDays(bloomDay, 1, 1));
        int[] bloomDay = {1, 10, 2, 9, 3, 8, 4, 7, 5, 6};
        System.out.println(new LeetCode1482().minDays(bloomDay, 4, 2));
    }

}
